#include<stdlib.h>
#include<stdio.h>
#include <memory.h> 
#include<string.h>

#define BOOL int
#define ArrayLen(x) sizeof(x)/sizeof(x[0])

#define MAXSIZE 40
#define LEN 1024

/*#define START 1
  #define VARIABLES 2
  #define DIGIT 3
  #define STRING 4
  #define LEFTCBRACKET 5
  #define RIGHTCBRACKET 6
  #define LEFTSBRACKET 7
  #define RIGHTSBRACKET 8*/

#define HashLength 1<<16

char *TreeTypeString[] =
  {
#include "KeyWords.h"
  };

typedef enum
  {
    NONE,
    NUM,
    DEFINE,
    START,
    VARIABLES,
    DIGIT,
    STRING,
    LEFTCBRACKET, //[
    RIGHTCBRACKET,//]
    LEFTSBRACKET ,//{
    RIGHTSBRACKET,//}
    INCLUDE ,
    DOT,          //.
    GREAT,        //>
    LESS,         //<
    NUMBER,
    IDENTITY,
    STAR,         //*
    SEMICOLON,    //,
    LEFTPARENTHESIS,      //(
    RIGHTPARENTHESIS,     //)
    LEFTQUOTE,    //'
    SHARP,        //#
    COLON,        //:
    UNDERSCORE,   //_
    SPACE,        //
    ENTERLINE,    //\n
    TAB,          //\t
    PLUS,         // +
    MINUS,        // -
    DIV,          ///
    ASSIGN,        // =
    EQUAL,       // ==  
    QMARK,        //?
    SLASH,        
    VBAR,          //|
    DOLLAR,       //$
    CARET,          //^
    AT,           //@
    TILDE,        //~
    AUTO,
    BREAK,
    CASE,
    CHAR,
    CONST,
    CONTINUE,
    DEFAULT,
    DO,
    DOUBLE,
    ELSE,
    ENUM,
    EXTERN,
    FLOAT,
    FOR,
    GOTO,
    IF,
    INLINE,
    INT,
    LONG,
    REGISTER,
    RESTRICT,
    RETURN,
    SHORT,
    SIGNED,
    SIZEOF,
    STATIC,
    STRUCT,
    SWITCH,
    TYPEDEF,
    UNION,
    UNSIGNED,
    VOID,
    VOLATILE,
    WHILE,
    COMMA
  }TreeType;


struct map
{
  char *name;
  TreeType t;
};

struct map xmap[] = {
  {"typedef",TYPEDEF},
  {"include",INCLUDE},
  {"auto",AUTO},
  {"break",BREAK},
  {"case",CASE},
  {"char",CHAR},
  {"const",CONST},
  {"continue",CONTINUE},
  {"default",DEFAULT},
  {"do",DO},
  {"double",DOUBLE},
  {"else",ELSE},
  {"enum",ENUM},
  {"extern",EXTERN},
  {"float",FLOAT},
  {"for",FOR},
  {"goto",GOTO},
  {"if",IF},
  {"inline",INLINE},
  {"int",INT},
  {"long",LONG},
  {"register",REGISTER},
  {"restrict",RESTRICT},
  {"return",RETURN},
  {"short",SHORT},
  {"signed",SIGNED},
  {"sizeof",SIZEOF},
  {"static",STATIC},
  {"struct",STRUCT},
  {"switch",SWITCH},
  {"typedef",TYPEDEF},
  {"union",UNION},
  {"unsigned",UNSIGNED},
  {"void",VOID},
  {"volatile",VOLATILE},
  {"while",WHILE },
  {"[",    LEFTCBRACKET},
  {"]",    RIGHTCBRACKET},
  {"{",    LEFTSBRACKET },
  {"}",    RIGHTSBRACKET},
  {".",    DOT},
  {">",    GREAT},
  {"<",    LESS},
  {"*",    STAR},
  {",",    COMMA},
  {";",    SEMICOLON},
  {"(",    LEFTPARENTHESIS},
  {")",    RIGHTPARENTHESIS},
  {"'",    LEFTQUOTE},
  {"#",    SHARP},
  {":",    COLON},
  {"_",    UNDERSCORE},
  {" ",    SPACE},
  {"\n",    ENTERLINE},
  {"\t",    TAB},
  {"+",    PLUS},
  {"-",    MINUS},
  {"",    DIV},
  {"=",    ASSIGN},
  {"==",   EQUAL},  
  {"?",    QMARK},
  {"\\",    SLASH},
  {"|",    VBAR},
  {"$",    DOLLAR},
  {"^",    CARET},
  {"@",    AT},
  {"~",    TILDE}
};


typedef struct token
{
  char name[40];
  TreeType t;
  int lineNumber;
  char *otherValue; // for string/chars type
}Token;

typedef struct hashBucket
{
  struct hashnode *next;
}HashBucket;

typedef struct hashnode
{
  char *name;
  int hashValue;
  TreeType t;
  struct hashnode *next;
  struct hashnode *startNode;
}HashNode;


int strlen(char *p);
Token * makeToken(char *p,TreeType t);
int HashString(char *p);
int sum(char buffer[]);
void initCharTable();
TreeType Get_Tree_Type(char *p);
void push_token_name_type(char *name,TreeType tType);
void push_token(char *name);
void SymbolParse(char c,FILE* fp);
void Move_End_Of_Line(char c,FILE* fp);
void SkipSpaceTab(FILE *fp);
void Skip_Command(char c,FILE* fp);
void Parse_Number(char c,FILE* fp);
void Skip_String(char t,FILE *fp);

void PrintFunction(int index);
void PrintFunctionPrev(int index);

//HashBucket hashTable[HashLength];

//**start global declaration
Token tokens[100000];
int tokenPointer = 0;
int lineNumber = 1;
//DFAState dfaState = NORMAL;

char* keyWords[]={"for","while","do","double","float","int","const","char","if","else","switch","case","include"};

char specialChar[]={'(',')',';','{','}','\\','/','#','*','\"','\'','=','-','<','>'};

char isValidateChar[256];
char isValidateStart[256];
char isSpeicalChar[256];
//**end global declaration

typedef struct stack
{
  char *tokenString;
  struct stack *next;
}Stack;

int xmapLength = sizeof(xmap)/sizeof(xmap[0]);

void DFA();
/*
  "#" means Macro parse start
 */
void MacroParse(FILE *fp);
void DefineParse(FILE *fp);
void MacroSkip(FILE *fp);
int mainRoutine();
BOOL  DirectoryList(char* Path);
int IsEndWithH(char *fullPath);
//

int main()
{
	//DirectoryList("D:\\downloads\\glib\\glib-2.0");
	//DirectoryList("D:\\downloads\\gtk\\gtk-2.0");
	DirectoryList("D:\\Lib\\gtk+-bundle_2.24.8-20111122_win32\\include");
	return 0;
}

int mainRoutine(char *fullpath) 
{ 
  FILE *fp;
  
  char *fileName = fullpath;
  memset(tokens,0,100000*sizeof(Token));
  tokenPointer = 0;
  lineNumber = 0;
  
  //"D:\\workspace\\c\\my-lib\\algorithm\\Introduction_to_Algorithms_Second_Edition\\GetSymbols\\GetSymbols.cpp";
  fp = fopen(fileName,"r");
  int i=0;
  char c;
  char charToString[2];
  //freopen("in.txt","r",stdin); 
  freopen("out.txt","a+",stdout);

  int State = START;

  initCharTable();

  if(fp==NULL)
    {
      printf("Open File %s Error",fileName);
      exit(1);
    }

  char *buffer = (char *)malloc(MAXSIZE*sizeof(char));

  for(i = 0;i<MAXSIZE;i++)
    {
      buffer[i] = 0;
    }
  i = 0;
  while ((c = fgetc(fp)) != EOF)
    {
      //to do: print out symbols

      switch(c)
        {
          //various name, key word
        case 'a': case 'b': case 'c': case 'd': case 'e': 
        case 'f': case 'g': case 'h': case 'i': case 'j': 
        case 'k': case 'l': case 'm': case 'n': case 'o': 
        case 'p': case 'q': case 'r': case 's': case 't': 
        case 'u': case 'v': case 'w': case 'x': case 'y': 
        case 'z': 
        case 'A': case 'B': case 'C': case 'D': case 'E': 
        case 'F': case 'G': case 'H': case 'I': case 'J': 
        case 'K': case 'L': case 'M': case 'N': case 'O': 
        case 'P': case 'Q': case 'R': case 'S': case 'T': 
        case 'U': case 'V': case 'W': case 'X': case 'Y': 
        case 'Z':
        case '_':
          SymbolParse(c,fp);
          break;

          //numbers;
        case '0': case '1': case '2': case '3': case '4': case '5': 
        case '6': case '7': case '8': case '9':
          Parse_Number(c,fp);
          break;

        case '#':
          //          dfaState = MACROSTATEMENT;
          //          charToString[0]=c;
          //          charToString[1]=0;
          //          push_token(charToString);
          MacroParse(fp);
          break;
          
        case '\"':
        case '\'':                    
          Skip_String(c,fp);
          break;

        //case '\t':
        case '(':
        case ')':
        case '{':
        case '}':
        case '[':
        case ']':
        case '<':
        case '>':
        case '+':
        case '-':
        case '*':
        case '=':
        case ':':
        case ';':
        case '\\':
        case '?':
        case ',':
        case '.':
        case '~':
        case '!':
        case '@':
        case '$':
        case '%':
        case '^':
        case '|':
          charToString[0]=c;
          charToString[1]=0;
          push_token(charToString);
          break;

        case '/':
          //deal with comment
          c=fgetc(fp);
          if(c=='/')
            {
              Move_End_Of_Line(c,fp);
              lineNumber++;
              //dealWithComment();
            }
          else if(c=='*')
            {
              Skip_Command(c,fp);
            }
          break;
        case '\n':
          lineNumber++;
          //          if(dfaState == MACROSTATEMENT) 
          //          {
          //push_token_name_type("\n",ENTERLINE);
          //dfaState = NORMAL;
          //}
          break;
        }
      //if(isValidateChar[c] == 1) 
      //	buffer[i++] = c;

      //if(isValidateChar[c] ==  0 && sum(buffer) != 0 )
      //{
      //	printf("%s\n",buffer);
      //	for(i = 0;i<MAXSIZE;i++)
      //	{
      //		buffer[i] = 0;
      //	}
      //	i = 0;
      //}
    }

  //for(i = 0;i<tokenPointer;i++)
  //  {
  //    printf("%s\t%s\t%d\n",tokens[i].name,TreeTypeString[tokens[i].t],tokens[i].lineNumber);
  //  }
  DFA();
  fclose(fp);
  return 0; 
}





void MacroParse(FILE *fp)
{
  char symbolTable[100];
  char c;
  int i = 0;
  memset(symbolTable,0,100);  
  while ((c = fgetc(fp)) != EOF)
    {
      if(isValidateChar[c] == 0)
        {
          ungetc(c,fp);
          break;
        }
      
      symbolTable[i++] = c;
    }
  if(strcmp(symbolTable,"define") == 0)
    DefineParse(fp);
  else
    MacroSkip(fp);
}

/*
  #define abc adsf\
  adsf\
  adsf
 */

void MacroSkip(FILE *fp)
{
  char c;
  char c1;
  char c2;
  while ((c = fgetc(fp)) != EOF)
    {
      if(c == '\\') 
        {
          c1 = fgetc(fp);
          c2 = fgetc(fp);
          if((c1 == '\r'&&c2 == '\n'))
            {
              continue;
            }
          else if(c1 == '\n') 
            {
              ungetc(c2,fp);
            }
          else
            {
              ungetc(c2,fp);
              ungetc(c1,fp);
            }
        }
      else if(c == '\n') 
          break;
    }
}

/*
  #define abc(x,y,z) x*y*z;
  Only try to get the define name and parameters.
 */
void DefineParse(FILE *fp)
{
  char symbolTable[100];
  char c;
  int i = 0;
  memset(symbolTable,0,100);
  SkipSpaceTab(fp);
  while ((c = fgetc(fp)) != EOF)
    {
      if(isValidateChar[c] == 0)
        {
          ungetc(c,fp);
          break;
        }
      
      symbolTable[i++] = c;
    }
  printf("%s",symbolTable);
  
  c = fgetc(fp);
  if(c == '(') 
    {
      printf("%c",c);
      while ((c = fgetc(fp)) != EOF)      
        {
          if(c == ')') 
            {
              printf("%c",c);
              break;
            }
          printf("%c",c);
        }
    }

  MacroSkip(fp);
  
  printf("---Macro\n");
}

void PrintTypedef(int index)
{
  int start = index; 
  int end;
  int i;
  while(index<tokenPointer)
    {
      if(tokens[index].t == SEMICOLON)
        {
          if(tokens[index - 1].t == IDENTITY) 
            printf("%s---TYPEDEF\n",tokens[index - 1].name);
          end = index - 1;
          break;
        }
      index++;
    }

  /*
    the following code will deal with the following problems.
    1. typedef (void *abc) (int def);
    2. typedef int def,ghi;
    move to ";" then determine what token before ";"
    if it is "IDENTITY" ,then the typedef type is type 2
    if it is ")", then the typedef type is type 1
   */
  if(tokens[end].t == RIGHTPARENTHESIS) 
    {
      int temp = 0;
      for(i = end;i>start;i--)
        {
          if(tokens[i].t == LEFTPARENTHESIS) 
            {
              temp = i+1;
              break;
            }
        }
      for(i = temp;i>start;i--)
        {
          if(tokens[i].t == RIGHTPARENTHESIS
             && tokens[i - 1].t == IDENTITY) 
            {
              printf("%s--- TYPEDEF\n",tokens[i - 1].name);
            }
        }
    }
  else if(tokens[end].t == IDENTITY)
    {
      for(i = end;i>start;i--)
        {
          if(tokens[i].t == COMMA)
            {
              if(tokens[i - 1].t == IDENTITY)
                {
                  printf("%s--- +  + TYPEDEF\n",tokens[i - 1].name);
                }
            }
        }
    }
  
}

void PrintFunction(int index)
{
  printf("---");
  int functionLevel = 0;

  //  TreeType tempSet[] = {SEMICOLON,LEFTSBRACKET};

  PrintFunctionPrev(index - 1);

  while(index<tokenPointer)
    {
      if(tokens[index].t == LEFTPARENTHESIS) 
        {
          functionLevel++;
        }
      if(tokens[index].t == RIGHTPARENTHESIS) 
        {
          printf("%s",tokens[index].name);
          if(functionLevel == 1) 
            break;

          functionLevel--;
        }
      printf("%s ",tokens[index].name);
      index++;
    }
  
  printf("\n");
}

void PrintFunctionPrev(int index)
{
  int tempIndex = index;

  while(tempIndex >= 0)
    {
      /*
        Determine the start of a function
        The macro is skiped, so we could not determine which is the start position of functions.
        This may be need to add more tokens to determine which one is start of a function.
        ; { }
       */
      if(tokens[tempIndex].t == SEMICOLON
         ||tokens[tempIndex].t == LEFTSBRACKET
         ||tokens[tempIndex].t == RIGHTSBRACKET) 
        {
          break;
        }
      tempIndex--;
    }
  tempIndex++;
  int i;
  for(i = tempIndex;i <= index;i++)
    {
      printf("%s ",tokens[i].name);
    }
}
/*
  struct { type declare; }
 */
void PrintStruct(int index)
{
  if(tokens[index + 1].t == IDENTITY && tokens[index + 2].t == LEFTSBRACKET) 
    printf("%s---struct\n",tokens[index + 1].name);
}

void DFA()
{
  int i=0;
  int functionLevel = 0;
  while(i<tokenPointer)
    {
      switch(tokens[i].t)
        {
        case LEFTPARENTHESIS:
          functionLevel++;
          if(tokens[i - 1].t == IDENTITY) 
            {
              if(functionLevel == 1)
                {
                  //printf("%s\t%s\t%d\n",tokens[i - 1].name,TreeTypeString[tokens[i - 1].t],tokens[i - 1].lineNumber);
                  //                  PrintFunctionPrev(i);
                  printf("%s",tokens[i - 1].name);
                  PrintFunction(i - 1);
                }
            }
          break;
        case RIGHTPARENTHESIS:
          functionLevel--;
          break;
        case TYPEDEF:
          PrintTypedef(i);
          break;
          
        case STRUCT:
          PrintStruct(i);
          break;
        }
      i++;
    }
}

int strlen(char *p)
{
  int i = 0;
  char *pt = p;

  for(;*pt != '\0';pt++)
    {
      i++;
    }
  return i;
}

Token * makeToken(char *p,TreeType t)
{
  char *pt = p;
  int index = 0;
  Token *token = (Token *)malloc(sizeof(Token));
  memset(token,0,sizeof(Token));

  if(strlen(p)<40)
    {
      for(;*pt != '\0';pt++)
        {
          token -> name[index++] = *pt; 
        }
      token -> name[index] = '\0'; 
    }
  token -> t = t;
  return token;
}

int HashString(char *p)
{
  char *s = p;
  int hashValue=0;
  while(*s!='\0')
    {
      hashValue += ((int)(*s))*((int)(*s));
      if(hashValue>HashLength)
        hashValue = hashValue%HashLength;
      s++;
    }
  return hashValue;
}

int sum(char buffer[])
{
  int i = 0;
  int temp = 0;
  for(i = 0;i<MAXSIZE;i++)
    {
      temp += buffer[i]; 
    }
  return temp;
}

void initCharTable()
{
  int i=0;

  for(i=0;i<256;i++)
    {
      isValidateStart[i]=0;
      isValidateChar[i]=0;
    }

  for(i = 'a';i <= 'z';i++)
    {
      isValidateChar[i] = 1;
      isValidateStart[i] = 1;
    }

  for(i = 'A';i <= 'Z';i++)
    {
      isValidateChar[i] = 1; 
      isValidateStart[i] = 1;
    }

  for(i='1';i<='9';i++)
    {
      isValidateChar[i] = 1; 
    }

  for(i=0;i<ArrayLen(specialChar);i++)
    {
      isSpeicalChar[specialChar[i]] = 1;
    }

  isValidateStart['_'] = 1;
  isValidateChar['_'] = 1;

}


TreeType Get_Tree_Type(char *p)
{
  int i = 0;
  for(i = 0;i<xmapLength;i++)
    {
      if(strcmp(xmap[i].name,p) == 0) 
        {
          return xmap[i].t;
        }
    }

  if((*p-'0'>0&&*p-'9'<0)||*p=='.')
    return NUM;
  return IDENTITY;
}

void push_token_name_type(char *name,TreeType tType)
{
  strcpy(tokens[tokenPointer].name,name);
  tokens[tokenPointer].t = tType;
  tokens[tokenPointer].lineNumber = lineNumber;
  tokenPointer++;
}

void push_token(char *name)
{
  TreeType tType = Get_Tree_Type(name);
  push_token_name_type(name,tType);
}


void SymbolParse(char c,FILE* fp)
{
  char symbolTable[100];
  memset(symbolTable,0,100);
  symbolTable[0] = c;
  int i = 1;
  while ((c = fgetc(fp)) != EOF)
    {
      if(isValidateChar[c] == 0)
        {
          ungetc(c,fp);
          break;
        }

      symbolTable[i++] = c;
    }
  //  printf("%s\n",symbolTable);
  push_token(symbolTable);
}

void Move_End_Of_Line(char c,FILE* fp)
{
  if(c=='\n')
    return;
	
  while ((c = fgetc(fp)) != EOF)
    {
      if(c=='\n')
        break;
    }
}

void SkipSpaceTab(FILE *fp)
{
  char c;
  while ((c = fgetc(fp)) != EOF)
    {
      if(c == ' ' || c == '\t')  
          continue;
      else
        {
          ungetc(c,fp);
          break;
        }
    }
}

void Skip_Command(char c,FILE* fp)
{
  char c1,c2;
  while ((c = fgetc(fp)) != EOF)
    {
      if(c=='*')
        {
          c=fgetc(fp);
          if(c=='/')
            return;
		  else
		  {
			  /*fix bug if \/***\/ it may not detect *\/ */
			ungetc(c,fp);
		  }
        }
      else if(c == '\n')
        lineNumber++;
    }
}

void Parse_Number(char c,FILE* fp)
{
  char *num=(char*)malloc(100);
  char *p=num;
  memset(num,0,100*sizeof(char));
  *p=c;
  p++;
  while ((c = fgetc(fp)) != EOF)
    {
      if((c-'0'>=0&&c-'9'<=0)||c=='.')
        {
          *p=c;
          p++;
        }
      else if(c==' '||c=='\t')
        break;

      else if(c=='\n')
        {
          lineNumber++;
          break;
        }
    }
  push_token(num);
}

void Skip_String(char t,FILE *fp)
{
  char c;
  while ((c = fgetc(fp)) != EOF)
    {
      if(c==t)
        break;
      else if(c=='\n')
        lineNumber++;
    }
}
